// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.collections;

public class DisjointSet {

	protected int[] p;

	protected int[] r;

	public DisjointSet(final int size) {
		p = new int[size];
		r = new int[size];
		for (int x = 0; x < size; x++) {
			p[x] = x;
			r[x] = 0;
		}
	}

	public void union(final int x, final int y) {
		link(findSet(x), findSet(y));
	}

	protected void link(final int x, final int y) {
		if (r[x] > r[y]) {
			p[y] = x;
		} else {
			p[x] = y;
			if (r[x] == r[y]) {
				r[y] = r[y] + 1;
			}
		}
	}

	public int findSet(final int x) {
		if (x != p[x]) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}

}
